// there is an image filled with 0s and 1s. There is at most one rectangle in this image filled with 0s, find the rectangle. Output could be the coordinates of top-left and bottom-right elements of the rectangle, or top-left element, width and height.
package main

import "fmt"

// for the same image, it is filled with 0s and 1s. It may have multiple rectangles filled with 0s. The rectangles are separated by 1s. Find all the rectangles.

// the image has random shapes filled with 0s, separated by 1s. Find all the shapes. Each shape is represented by coordinates of all the elements inside.

func atMostOneRectangle(image [][]int) [][2]int {
	res := [][2]int{}

	for i := 0; i < len(image); i++ {
		for j := 0; j < len(image[i]); j++ {
			if image[i][j] == 0 {
				// find the size of this rectangle
				topLeft := [2]int{i, j}
				height, width := 1, 1
				for j+width < len(image[i]) && image[i][j+width] == 0 {
					width++
				}
				for i+height < len(image) {
					if image[i+height][j] == 0 {
						allZeroFlag := true
						for x := j + 1; x < j+width; x++ {
							if image[i+height][x] != 0 {
								allZeroFlag = false
							}
						}
						if allZeroFlag == true {
							height++
						} else {
							break
						}
					} else {
						break
					}
				}
				res = append(res, topLeft)
				res = append(res, [2]int{i + height - 1, j + width - 1})
				return res
			}
		}
	}
	return res
}

func findMultiple(image [][]int) [][][2]int {
	res := [][][2]int{}

	for i := 0; i < len(image); i++ {
		for j := 0; j < len(image[i]); j++ {
			if image[i][j] == 0 {
				rec := [][2]int{[2]int{i, j}}
				height, width := 1, 1
				image[i][j] = 1
				for i+height < len(image) && image[i+height][j] == 0 {
					height++
				}
				for j+width < len(image[i]) && image[i][j+width] == 0 {
					width++
				}
				// if image[i+height-1][j+width-1] == 0 {
				rec = append(rec, [2]int{i + height - 1, j + width - 1})
				res = append(res, rec)
				for h := 0; h < height; h++ {
					for w := 0; w < width; w++ {
						image[i+h][j+w] = 1
					}
				}
				// }

			}
		}
	}
	return res
}

func findAllShapes(image [][]int) [][][2]int {
	queue := [][2]int{}

	for i := 0; i < len(image); i++ {
		for j := 0; j < len(image[i]); j++ {
			if image[i][j] == 0 {
				queue = append(queue, [2]int{i, j})
				image[i][j] = 1
				width := 1
				for j+width < len(image[i]) {
					if image[i][j+width] == 0 {
						queue = append(queue, [2]int{i, j + width})
						image[i][j+width] = 1
						width++
					}
					tempQueue := [][2]int{}
					for len(queue) != 0 {
						for x := 0; x < len(queue); x++ {
							if x == 0 || x == len(queue)-1 {

							} else {
								if queue[x][0]+1 < len(image) && image[queue[x][0]+1][queue[x][1]] == 0 {
									tempQueue = append(tempQueue)
								}
							}
						}
					}
				}

			}
		}
	}
}
func main() {
	input := [][]int{
		[]int{0, 0, 1, 0, 0},
		[]int{0, 0, 0, 0, 0},
	}
	input2 := [][]int{
		[]int{1, 1, 1, 0, 0},
		[]int{1, 1, 1, 0, 0},
	}
	input3 := [][]int{
		{1, 1, 1, 1, 1, 1, 1},
		{1, 1, 1, 1, 1, 1, 1},
		{1, 1, 1, 0, 0, 0, 1},
		{1, 1, 1, 0, 0, 0, 1},
		{1, 1, 1, 1, 1, 1, 0},
	}
	input4 := [][]int{
		{0},
	}
	// [[1,1,1,1,1],
	// [1,0,0,1,1],
	// [1,0,0,1,1],
	// [1,1,1,1,0]], you should return [[[1,1],[2,2]],[[3,4],[3,4]]]
	fmt.Println(atMostOneRectangle(input))
	fmt.Println(atMostOneRectangle(input2))
	fmt.Println(atMostOneRectangle(input3))
	fmt.Println(atMostOneRectangle(input4))

	fmt.Println(findMultiple(input3))
}

/*

Imagine we have an image. We'll represent this image as a simple 2D array where every pixel is a 1 or a 0. The image you get is known to have a single rectangle of 0s on a background of 1s.

Write a function that takes in the image and returns one of the following representations of the rectangle of 0's: top-left coordinate and bottom-right coordinate OR top-left coordinate, width, and height.

image1 = [
  [1, 1, 1, 1, 1, 1, 1],
  [1, 1, 1, 1, 1, 1, 1],
  [1, 1, 1, 0, 0, 0, 1],
  [1, 1, 1, 0, 0, 0, 1],
  [1, 1, 1, 1, 1, 1, 1],
]

Sample output variations (only one is necessary):

findRectangle(image1) =>
  x: 3, y: 2, width: 3, height: 2
  2,3 3,5 -- row,column of the top-left and bottom-right corners

Other test cases:

image2 = [
  [1, 1, 1, 1, 1, 1, 1],
  [1, 1, 1, 1, 1, 1, 1],
  [1, 1, 1, 1, 1, 1, 1],
  [1, 1, 1, 1, 1, 1, 1],
  [1, 1, 1, 1, 1, 1, 0],
]

findRectangle(image2) =>
  x: 6, y: 4, width: 1, height: 1
  4,6 4,6

image3 = [
  [1, 1, 1, 1, 1, 1, 1],
  [1, 1, 1, 1, 1, 1, 1],
  [1, 1, 1, 1, 1, 1, 1],
  [1, 1, 1, 1, 1, 0, 0],
  [1, 1, 1, 1, 1, 0, 0],
]

findRectangle(image3) =>
  x: 5, y: 3, width: 2, height: 2
  3,5 4,6

image4 = [
  [0, 1, 1, 1, 1, 1, 1],
  [1, 1, 1, 1, 1, 1, 1],
  [1, 1, 1, 1, 1, 1, 1],
  [1, 1, 1, 1, 1, 1, 1],
  [1, 1, 1, 1, 1, 1, 1],
]

findRectangle(image4) =>
  x: 0, y: 0, width: 1, height: 1
  0,0 0,0

image5 = [
  [0],
]

findRectangle(image5) =>
  x: 0, y: 0, width: 1, height: 1
  0,0 0,0

n: number of rows in the input image
m: number of columns in the input image

*/
